//
//  Solution394.swift
//  swiftDemo
//
//  Created by JIENING ZHANG on 2022/11/9.
//  Copyright © 2022 lovivid. All rights reserved.
//

import UIKit

/*
 给定一个经过编码的字符串，返回它解码后的字符串。

 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

  

 示例 1：

 输入：s = "3[a]2[bc]"
 输出："aaabcbc"
 示例 2：

 输入：s = "3[a2[c]]"
 输出："accaccacc"
 示例 3：

 输入：s = "2[abc]3[cd]ef"
 输出："abcabccdcdcdef"
 示例 4：

 输入：s = "abc3[cd]xyz"
 输出："abccdcdcdxyz"
  

 提示：

 1 <= s.length <= 30
 s 由小写英文字母、数字和方括号 '[]' 组成
 s 保证是一个 有效 的输入。
 s 中所有整数的取值范围为 [1, 300]

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/decode-string
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

// Swift中 Character https://www.jianshu.com/p/86d591cae1bf

class DecodeTreeNode: NSObject {
    var repeatNum:Int = 1;
    var repeatStr = "";
    var parentNode:DecodeTreeNode? = nil;
    var subNodes:[DecodeTreeNode] = [];
}

class Solution394: NSObject {
    func decodeString(_ s: String) -> String {
        
        //        输入：s = "3[a]2[bc]"
        //        输出："aaabcbc"
        //        输入：s = "3[a2[c]]"
        //        输出："accaccacc"
        //        输入：s = "2[abc]3[cd]ef"
        //        输出："abcabccdcdcdef"
        //        输入：s = "abc3[cd]xyz"
        //        输出："abccdcdcdxyz"
        
        // 构建 DecodeTree 的 root节点
        var root:DecodeTreeNode = DecodeTreeNode();
        var currentNode = root;
        
        var rNumStr = "";
        var rStr = "";
        
        // 构建 DecodeTree
        for char in s {
            if char == Character("[") {
                
                // 构建新的 子节点 挂到 currentnode
                let subNode = DecodeTreeNode();
                if let rNum = Int(rNumStr) {
                    subNode.repeatNum = rNum;
                } else {
                    subNode.repeatNum = 1;
                }
                subNode.parentNode = currentNode;
                currentNode.subNodes.append(subNode);
                
                // 然后将 currentnode 指向 子节点，直到 遇到 ] ，currentnode 指回 当前节点
                currentNode = subNode;
                rNumStr = "";
                
            } else if char == Character("]") {
                
                if currentNode.subNodes.count > 0 {
                    //比如 3[a2[c]dd4[t]pp] 读取最右边的方括号时, rStr = pp, rStr 生成新的节点
                    let subNode = DecodeTreeNode();
                    subNode.repeatNum = 1;
                    subNode.repeatStr = rStr;
                    subNode.parentNode = currentNode;
                    currentNode.subNodes.append(subNode);
                } else {
                    //比如 3[a2[c]dd4[t]pp] 读取从右到左第二个方括号时, rStr = t，rStr 赋值给 repeatStr
                    currentNode.repeatStr = rStr;
                }
                
                // currentnode 指回
                if let pNode = currentNode.parentNode {
                    currentNode = pNode;
                }
                
                rStr = "";
                
            } else if char >= Character("0") && char <= Character("9") {
                
                rNumStr += String(char);
                if rStr.count > 0 {
                    // 读到数字时，字符非空，例如 s = "3[a2[c]dd4[t]]", 读取数字2 和 4 的时候
                    
                    let subNode = DecodeTreeNode();
                    subNode.repeatNum = 1;
                    subNode.repeatStr = rStr;
                    subNode.parentNode = currentNode;
                    currentNode.subNodes.append(subNode);
                    rStr = "";
                    
                }
                
            } else {
                
                rStr += String(char);
            }
        }
        
        if rStr.count > 0 {
            // 完成 入参字符串遍历 rStr非空，构建一个新的子节点
            
            let subNode = DecodeTreeNode();
            subNode.repeatNum = 1;
            subNode.repeatStr = rStr;
            subNode.parentNode = currentNode;
            currentNode.subNodes.append(subNode);
            rStr = "";
        }
        
        var rtnStr = goThrouthDecodeTree(root);
        
        return rtnStr;
    }
    
    func goThrouthDecodeTree(_ node: DecodeTreeNode) -> String {
        var rtnStr = "";
        
        if node.subNodes.count > 0 {
            // 非 叶子节点
            
            // 递归构建 重复字符串
            var repeatStr = "";
            for subNode in node.subNodes {
                repeatStr += goThrouthDecodeTree(subNode);
            }
            
            for loop in 0 ..< node.repeatNum {
                rtnStr += repeatStr;
            }
        } else {
            // 叶子节点
            // 3[a2[c]dd4[t]pp] --> repeatNum:3, subNodes: (a) (2,c) (dd) (4,t) (pp)
            for loop in 0 ..< node.repeatNum {
                rtnStr += node.repeatStr;
            }
        }
    
        return rtnStr;
    }
}
